package day2;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;

public class ch3 {

    //53
    public int maxSubArray(int[] nums) {
        int[] arr = new int[nums.length];
        arr[0] = nums[0];
        int max = 0;
        for (int i = 1; i < nums.length; i++) {
            arr[i] = Math.max(arr[i - 1] + nums[i], nums[i]);
            max = Math.max(max, arr[i]);
        }
        return max;


    }

    //56
    public int[][] merge(int[][] intervals) {
        int len = intervals.length;
        List<int[]> list = new ArrayList<>();
        Arrays.sort(intervals,(a,b)->{return a[0]==b[0]?a[1]-b[1]:a[0]-b[0];});

        int[] b= intervals[0];
        for (int i = 1; i < len; i++) {
            int[] a = intervals[i];
            if(b[1]<a[0]){

                list.add(Arrays.copyOf(b,b.length));
                b=a;
            }else {
                b[0]=Math.min(b[0],a[0]);
                b[1]=Math.max(b[1],a[1]);
            }
        }

        int n = list.size();
        int[][] x= new int[n][2];
        for (int i = 0; i < n; i++) {
            x[i] = list.get(i);
        }

        return x;

    }

    //189
    public void rotate(int[] nums, int k) {
        rev(nums,0,nums.length-1);
        rev(nums,0,k-1);
        rev(nums,k,nums.length-1);


    }

    public void rev(int[] arr,int begin,int end){
        while (begin<end){
            int n = arr[begin];
            arr[begin] = arr[end];
            arr[end] = n;
            begin++;
            end--;
        }
    }


    //238
    public int[] productExceptSelf(int[] nums) {
        int len = nums.length;
        int[] arr = new int[len];
        arr[len-1] = 1;
        for (int i = len-2; i >= 0; i--) {
            arr[i] = arr[i-1]*nums[i-1];
        }
        int num=1;
        for (int i = 0; i < len; i++) {
            arr[i] = num*arr[i];
            num *= nums[i];
        }

        return arr;

    }

    //41
    public int firstMissingPositive(int[] nums) {
        int len = nums.length;
        for (int i = 0; i < len; i++) {
            if(nums[i] < 0){
                nums[i] = len+1;
            }
        }
        for (int i = 0; i < len; i++) {
            int n = Math.abs(nums[i]);
            if(n>0&&n<=len){
                nums[n-1] = -Math.abs(nums[n-1]);
            }
        }

        for (int i = 0; i < len; i++) {
            int n = nums[i];
            if(n>0){
                return n;
            }
        }

        return len+1;

    }



}
